package com.zhenti.z1;
// 来自腾讯
// 给定一个字符串str，和一个正数k
// 返回长度为k的所有子序列中，字典序最大的子序列
public class zhenti_P10 {
    public static void main(String[] args) {
        String s = "asddddssssaxzxz";
        System.out.println(maxString(s, 3));
    }

    public static String maxString(String s,int k){
        if (s.length()<k || k <= 0)
            return "";
        int l = s.length();
        char[] str = s.toCharArray();
        char[]  stack = new char[l];
        int size = 0;
        for (int i = 0; i < l; i++) {
            while (size > 0 && stack[size-1] < str[i] && size + l -i > k){
                size --;
            }
            if (size + l - i == k){
                return String.valueOf(stack,0,size) + s.substring(i);
            }
            stack[size++] = str[i];
        }
        return String.valueOf(stack,0,k);
    }
}
